package demo;

import java.util.*;

public class BinaryTree_int {
    static class TreeNode {

        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode creat(){
        TreeNode A=new TreeNode(3);
        TreeNode B=new TreeNode(9);
        TreeNode C=new TreeNode(20);
        TreeNode D=new TreeNode(15);
        TreeNode E=new TreeNode(7);
        A.left=B;
        A.right=C;
        C.left=E;
        C.right=D;
        return A;

    }


    public List<List<Integer>> levelOrderBottom(BinaryTree_int.TreeNode root) {
        List<List<Integer>>ret=new ArrayList<>();
        Queue<TreeNode>queue=new LinkedList<>();
        TreeNode cur=null;
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer>level=new ArrayList<>();
            int se=queue.size();
            while(se>0){
                //弹一个就入层
                cur=queue.poll();
                level.add(cur.val);

                if(cur.left!=null){
                    queue.add(cur.left);
                }
                if(cur.right!=null){
                    queue.add(cur.right);
                }
                se--;
            }
            ret.add(0,level);
        }
        return ret;
    }
}
